package dynamicProgramming.review6_1;

public class BagProblem1 {

    public  static  void   test(int[] weight,int[]  value,int bagSize){

        int goods = weight.length;
    int[][] dp=new int[goods][bagSize+1];


    //  CKG TODO 2023/6/1:  包的价值大于第一个物品的重量之后才开始有ｉ价值
        for (int i = weight[0]; i <=bagSize ; i++) {
            dp[0][i]=value[0];
        }

        //  CKG TODO 2023/6/1: 填充dp 数组
        //  CKG TODO 2023/6/1: 先遍历物品
        for (int i = 1; i < weight.length; i++) {
            //  CKG TODO 2023/6/1: 再遍历每个物品下不同质量的背包能装的最大价值
            for (int j = 1; j <=bagSize ; j++) {
                if (j<weight[i]){
                    //  CKG TODO 2023/6/1:  装不下的时候　　为上一行的数值
                    dp[i][j]=dp[i-1][j];
                }
                else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i]);
                }
            }
        }

        for (int i = 0; i <goods ; i++) {
            for (int j = 0; j <=bagSize ; j++) {
                System.out.println(dp[i][j]+"\t");
            }
            System.out.println("\n");

        }








    }

    public static void main(String[] args) {

        int[] weight={1,3,4};
        int[]  value={15,20,30};

        int bagSize=4;
        test(weight,value,bagSize);


    }



}
